package  main.java.leetcode.editor.cn;
//2023-07-03 09:10:14
//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 
//
// 
//
// 示例1： 
//
// 
//
// 
//输入：l1 = [7,2,4,3], l2 = [5,6,4]
//输出：[7,8,0,7]
// 
//
// 示例2： 
//
// 
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[8,0,7]
// 
//
// 示例3： 
//
// 
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 100] 
// 0 <= node.val <= 9 
// 输入数据保证链表代表的数字无前导 0 
// 
//
// 
//
// 进阶：如果输入链表不能翻转该如何解决？ 
// Related Topics 栈 链表 数学 👍 614 👎 0

import java.util.ArrayDeque;
import java.util.Deque;

class AddTwoNumbersIi {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new AddTwoNumbersIi().new Solution();
        ListNode headA = new ListNode(7);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(4);
        headA.next.next.next = new ListNode(3);

        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(4);
        solution.addTwoNumbers(headA,headB);
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();

        ListNode cur1 = l1;
        ListNode cur2 = l2;
        while (cur1 != null){
            stack1.offerLast(cur1.val);
            cur1 = cur1.next;
        }

        while (cur2 != null){
            stack2.offerLast(cur2.val);
            cur2 = cur2.next;
        }

        int sign = 0;
        ListNode head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || sign != 0){
            int val1 = stack1.isEmpty() ? 0 : stack1.pollLast();
            int val2 = stack2.isEmpty() ? 0 : stack2.pollLast();

            int val = val1+val2+sign;

            sign = val/10;
            val = val%10;

            ListNode node = new ListNode(val);
            node.next = head;
            head = node;
        }
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
